// sparse matrix 
#include <vector>
#include <algorithm>
#include <climits>
#include "kddcup_feat.h"

class SMatrix{
public:
    struct Edge{
        int from, to;
        inline bool operator<( const Edge &p ) const{
            if( from < p.from ) return true;
            if( from > p.from ) return false;
            return to < p.to;
        }
    };
    struct Row{
        int nlen;
        const int *index;
    };
private:
    std::vector<unsigned> row_ptr;
    std::vector<int> findex;
public:
    inline size_t num_entry( void )const{
        return findex.size();
    }
    inline size_t num_row( void )const{
        return row_ptr.size()-1;
    }
    inline void build( std::vector< Edge > &data, int num_node ){
        row_ptr.clear(); findex.clear(); row_ptr.push_back( 0 );
        std::sort( data.begin(), data.end() );
        size_t top = 0;
        for( int i = 0; i < num_node; i ++ ){
            size_t j = top;
            while( j < data.size() && data[j].from == i ){
                findex.push_back( data[j].to );
                j ++;
            }
            row_ptr.push_back( top = j );
        }
        printf("load graph with %d nodes, %d edges\n", num_node, (int)findex.size() );
    }
    inline void load( const char *fname, int num_node, int num_item = INT_MAX, int minid = 0 ){
        Edge e;
        std::vector< Edge > data;
        FILE *fi = fopen_check( fname, "r" );
        while( fscanf( fi, "%d%d%*[^\n]\n", &e.from, &e.to ) == 2 ){
            if( e.to >= num_item ) continue;
            if( e.to < minid || e.from < minid ) continue; 
            data.push_back( e );
        } 
        fclose( fi );
        this->build( data, num_node );
    }
    inline size_t get_index( const int *idx ){
        return (idx - &findex[0]);
    }
    inline int get_index( int from, int to ){
        int nlen = row_ptr[ from + 1 ] - row_ptr[ from ]; 
        int *rindex = &findex[ row_ptr[ from ] ];
        size_t idx = std::lower_bound( rindex, rindex + nlen, to ) - rindex;
        if( idx < (size_t)nlen && rindex[idx] == to ){
            return (int)get_index( &rindex[idx] );
        }else{
            return -1;
        }
    }
    Row operator[]( int index ) const{
        Row row;
        row.nlen = row_ptr[ index + 1 ] - row_ptr[ index ]; 
        row.index = &findex[ row_ptr[ index ] ];
        return row;
    }    
};
